package com.lsa.letcode.the91.decodeWays;

import java.util.HashMap;
import java.util.Map;

public class Solution {
	private Map<Integer, Integer> memo = new HashMap<Integer, Integer>();
	
    public int numDecodings(String s) {
    	if (s.length() < 1) {
    		return 0; 
    	}
    	
    	return recurseCombinations(s, 0);
    }
    
    private int recurseCombinations(String s, int from) {
    	if (from >= s.length()) {
    		return 1;
    	}
    	Integer count = memo.get(from);
    	if (count != null) {
    		return count;
    	}
    	else {
    		count = 0;
    	}
    	
    	if (checkSubstring(s, from, from + 1)) {
    		count += recurseCombinations(s, from + 1);
    	}
    	
    	if (from + 2 <= s.length() ) {
    		if (checkSubstring(s, from, from + 2)) {
    			count += recurseCombinations(s, from + 2);
    		}
    	}
    	
    	memo.put(from, count);
    	
    	return count;
    }

	private static boolean checkSubstring(String s, int from, int to) {
		String sub = s.substring(from, to);
		
		int num = 0;
		for (int j = 0; j < sub.length(); j++) {
			char c = sub.charAt(j);
			if (c < '0' || c > '9') {
				return false;
			}
			num = num * 10 + (c - '0');
			if (1 > num || 26 < num) {
				return false;
			}
		}
		
		if (num < 10 && sub.length() != 1) {
			return false;
		}
		if (num > 9 && sub.length() != 2) {
			return false;
		}
		return true;
	}
}

/*
  1 2 3
 () ( )
 
  1 2 3
 (  )()
 
  1 2 3
 ()()()
*/